package recursion;

import java.util.Queue;

public class EightQueens {
	//定义一个 max 表示共有多少个皇后
	int max = 8;
	//定义一个数组array，保存皇后存放的位置结果
	int[] array = new int[max];

	public static void main(String[] args) {
		//测试
		EightQueens eightQueens = new EightQueens();
		eightQueens.check(0);


	}

	//写一个方法，将皇后摆放的位置打印出来
	private void print() {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}

	//查看放置第 N 个皇后时，检查是否与之前的皇后存在冲突
	private boolean judge(int n) {
		for (int i = 0; i < n; i++) {
			if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
				// 1.判断是否在同一列      2.判断第 n 个是否和第 i 个是否在同一斜线
				return false;
			}
		}
		return true;
	}

	//放置第 n 个皇后
	private void check(int n) {
		if (n == max) {
			//成立，则已经放置完成，结束
			print();
			return;
		}
		//没有结束，依次放入并判断是否冲突
		for (int i = 0; i < max; i++) {
			//先把当前这个皇后，放到该行的第一列
			array[n] = i;
			//判断当放置第 n 个皇后，后是否冲突
			if (judge(n)) {
				//若不冲突，接着放下一个,开始递归
				check(n + 1);
			} else {
				//若冲突就继续循环，把皇后往后放一个
				continue;
			}
		}
	}

}
